#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param A: An integer array
    @return: An integer
    """
    def singleNumberII(self, A):
        # write your code here
        self.record = [0] * 33

        for i in A:
            self.record_ele(i)

        return self.find()

    def record_ele(self, n):
        if n < 0:
            n = -n
            self.record[0] += 1

        i = 1

        remain, n = n % 2, n // 2
        self.record[i] += remain

        # print(n)
        while n:
            # print(i)
            i += 1
            remain, n = n % 2, n // 2
            self.record[i] += remain
        return

    def find(self):
        # 找出唯一的一个数
        result = 0
        if self.record[0] % 3 == 0:
            sign = 1
        else:
            sign = -1

        for i, cnt in enumerate(self.record[1:], 0):
            if cnt % 3 != 0:
                result += 2 ** (i)

        return sign * result


def main():
    print("start main")
    s = Solution()
    # ret = s.singleNumberII([1,1,2,3,3,3,2,2,4,1])
    ret = s.singleNumberII( [43,16,45,89,45,-2147483648,45,2147483646,-2147483647,-2147483648,43,2147483647,-2147483646,-2147483648,89,-2147483646,89,-2147483646,-2147483647,2147483646,-2147483647,16,16,2147483646,43])
    print(ret)

if __name__ == "__main__":
    main()
